#include "CostumUtils.h"
#include <vector>

using std::vector;

int partition(vector<int> &list, int begin, int end);
int randomizedPartition(vector<int> &list, int begin, int end);

void quickSort(vector<int> &list, int begin, int end)
{
	if (begin < end) {
		int mid = partition(list, begin, end);
		quickSort(list, begin, mid - 1);
		quickSort(list, mid + 1, end);
	}
}


/*

 i  p j                    r 
   | 2  8  7  1  3  5  6 | 4
   p = begin, r = end.
*/
int partition(vector<int> &list, int begin, int end)
{
	int x = list[end];
	int i = begin - 1;
	for (int j = begin; j <= end - 1; j++){
		if (list[j] <= x) {
			i++;
			std::swap(list[i], list[j]);
		}
	}
	EXCHANGE(list[i + 1], list[end]);
	return i + 1;
}

//random version
int randomizedPartition(vector<int> &list, int begin, int end)
{
	//int i = random(begin, end); generate a random number between begin and end;
	//EXCHANGE(list[i], list[end]);
	return partition(list, begin, end);
}